home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / flex_247.zip / flex_247 / dfa.c < prev    next >
C/C++ Source or Header  |  1994-01-04  |  26KB  |  1,086 lines
  1. /* dfa - DFA construction routines */
  2.  
  3. /*-
  4.  * Copyright (c) 1990 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant
  11.  * to contract no. DE-AC03-76SF00098 between the United States
  12.  * Department of Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted provided
  15.  * that: (1) source distributions retain this entire copyright notice and
  16.  * comment, and (2) distributions including binaries display the following
  17.  * acknowledgement:  ``This product includes software developed by the
  18.  * University of California, Berkeley and its contributors'' in the
  19.  * documentation or other materials provided with the distribution and in
  20.  * all advertising materials mentioning features or use of this software.
  21.  * Neither the name of the University nor the names of its contributors may
  22.  * be used to endorse or promote products derived from this software without
  23.  * specific prior written permission.
  24.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  25.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  26.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  27.  */
  28.  
  29. /* $Header: dfa.c,v 1.2 94/01/04 14:33:16 vern Exp $ */
  30.  
  31. #include "flexdef.h"
  32.  
  33.  
  34. /* declare functions that have forward references */
  35.  
  36. void dump_associated_rules PROTO((FILE*, int));
  37. void dump_transitions PROTO((FILE*, int[]));
  38. void sympartition PROTO((int[], int, int[], int[]));
  39. int symfollowset PROTO((int[], int, int, int[]));
  40.  
  41.  
  42. /* check_for_backing_up - check a DFA state for backing up
  43.  *
  44.  * synopsis
  45.  *     void check_for_backing_up( int ds, int state[numecs] );
  46.  *
  47.  * ds is the number of the state to check and state[] is its out-transitions,
  48.  * indexed by equivalence class.
  49.  */
  50.  
  51. void check_for_backing_up( ds, state )
  52. int ds;
  53. int state[];
  54.     {
  55.     if ( (reject && ! dfaacc[ds].dfaacc_set) ||
  56.          (! reject && ! dfaacc[ds].dfaacc_state) )
  57.         { /* state is non-accepting */
  58.         ++num_backing_up;
  59.  
  60.         if ( backing_up_report )
  61.             {
  62.             fprintf( backing_up_file,
  63.                 "State #%d is non-accepting -\n", ds );
  64.  
  65.             /* identify the state */
  66.             dump_associated_rules( backing_up_file, ds );
  67.  
  68.             /* Now identify it further using the out- and
  69.              * jam-transitions.
  70.              */
  71.             dump_transitions( backing_up_file, state );
  72.  
  73.             putc( '\n', backing_up_file );
  74.             }
  75.         }
  76.     }
  77.  
  78.  
  79. /* check_trailing_context - check to see if NFA state set constitutes
  80.  *                          "dangerous" trailing context
  81.  *
  82.  * synopsis
  83.  *    void check_trailing_context( int nfa_states[num_states+1], int num_states,
  84.  *                int accset[nacc+1], int nacc );
  85.  *
  86.  * NOTES
  87.  *  Trailing context is "dangerous" if both the head and the trailing
  88.  *  part are of variable size \and/ there's a DFA state which contains
  89.  *  both an accepting state for the head part of the rule and NFA states
  90.  *  which occur after the beginning of the trailing context.
  91.  *
  92.  *  When such a rule is matched, it's impossible to tell if having been
  93.  *  in the DFA state indicates the beginning of the trailing context or
  94.  *  further-along scanning of the pattern.  In these cases, a warning
  95.  *  message is issued.
  96.  *
  97.  *    nfa_states[1 .. num_states] is the list of NFA states in the DFA.
  98.  *    accset[1 .. nacc] is the list of accepting numbers for the DFA state.
  99.  */
  100.  
  101. void check_trailing_context( nfa_states, num_states, accset, nacc )
  102. int *nfa_states, num_states;
  103. int *accset;
  104. register int nacc;
  105.     {
  106.     register int i, j;
  107.  
  108.     for ( i = 1; i <= num_states; ++i )
  109.         {
  110.         int ns = nfa_states[i];
  111.         register int type = state_type[ns];
  112.         register int ar = assoc_rule[ns];
  113.  
  114.         if ( type == STATE_NORMAL || rule_type[ar] != RULE_VARIABLE )
  115.             { /* do nothing */
  116.             }
  117.  
  118.         else if ( type == STATE_TRAILING_CONTEXT )
  119.             {
  120.             /* Potential trouble.  Scan set of accepting numbers
  121.              * for the one marking the end of the "head".  We
  122.              * assume that this looping will be fairly cheap
  123.              * since it's rare that an accepting number set
  124.              * is large.
  125.              */
  126.             for ( j = 1; j <= nacc; ++j )
  127.                 if ( accset[j] & YY_TRAILING_HEAD_MASK )
  128.                     {
  129.                     line_warning(
  130.                         "dangerous trailing context",
  131.                         rule_linenum[ar] );
  132.                     return;
  133.                     }
  134.             }
  135.         }
  136.     }
  137.  
  138.  
  139. /* dump_associated_rules - list the rules associated with a DFA state
  140.  *
  141.  * Goes through the set of NFA states associated with the DFA and
  142.  * extracts the first MAX_ASSOC_RULES unique rules, sorts them,
  143.  * and writes a report to the given file.
  144.  */
  145.  
  146. void dump_associated_rules( file, ds )
  147. FILE *file;
  148. int ds;
  149.     {
  150.     register int i, j;
  151.     register int num_associated_rules = 0;
  152.     int rule_set[MAX_ASSOC_RULES + 1];
  153.     int *dset = dss[ds];
  154.     int size = dfasiz[ds];
  155.  
  156.     for ( i = 1; i <= size; ++i )
  157.         {
  158.         register int rule_num = rule_linenum[assoc_rule[dset[i]]];
  159.  
  160.         for ( j = 1; j <= num_associated_rules; ++j )
  161.             if ( rule_num == rule_set[j] )
  162.                 break;
  163.  
  164.         if ( j > num_associated_rules )
  165.             { /* new rule */
  166.             if ( num_associated_rules < MAX_ASSOC_RULES )
  167.                 rule_set[++num_associated_rules] = rule_num;
  168.             }
  169.         }
  170.  
  171.     bubble( rule_set, num_associated_rules );
  172.  
  173.     fprintf( file, " associated rule line numbers:" );
  174.  
  175.     for ( i = 1; i <= num_associated_rules; ++i )
  176.         {
  177.         if ( i % 8 == 1 )
  178.             putc( '\n', file );
  179.  
  180.         fprintf( file, "\t%d", rule_set[i] );
  181.         }
  182.  
  183.     putc( '\n', file );
  184.     }
  185.  
  186.  
  187. /* dump_transitions - list the transitions associated with a DFA state
  188.  *
  189.  * synopsis
  190.  *     dump_transitions( FILE *file, int state[numecs] );
  191.  *
  192.  * Goes through the set of out-transitions and lists them in human-readable
  193.  * form (i.e., not as equivalence classes); also lists jam transitions
  194.  * (i.e., all those which are not out-transitions, plus EOF).  The dump
  195.  * is done to the given file.
  196.  */
  197.  
  198. void dump_transitions( file, state )
  199. FILE *file;
  200. int state[];
  201.     {
  202.     register int i, ec;
  203.     int out_char_set[CSIZE];
  204.  
  205.     for ( i = 0; i < csize; ++i )
  206.         {
  207.         ec = ABS( ecgroup[i] );
  208.         out_char_set[i] = state[ec];
  209.         }
  210.  
  211.     fprintf( file, " out-transitions: " );
  212.  
  213.     list_character_set( file, out_char_set );
  214.  
  215.     /* now invert the members of the set to get the jam transitions */
  216.     for ( i = 0; i < csize; ++i )
  217.         out_char_set[i] = ! out_char_set[i];
  218.  
  219.     fprintf( file, "\n jam-transitions: EOF " );
  220.  
  221.     list_character_set( file, out_char_set );
  222.  
  223.     putc( '\n', file );
  224.     }
  225.  
  226.  
  227. /* epsclosure - construct the epsilon closure of a set of ndfa states
  228.  *
  229.  * synopsis
  230.  *    int *epsclosure( int t[num_states], int *numstates_addr,
  231.  *            int accset[num_rules+1], int *nacc_addr,
  232.  *            int *hashval_addr );
  233.  *
  234.  * NOTES
  235.  *  The epsilon closure is the set of all states reachable by an arbitrary
  236.  *  number of epsilon transitions, which themselves do not have epsilon
  237.  *  transitions going out, unioned with the set of states which have non-null
  238.  *  accepting numbers.  t is an array of size numstates of nfa state numbers.
  239.  *  Upon return, t holds the epsilon closure and *numstates_addr is updated.
  240.  *  accset holds a list of the accepting numbers, and the size of accset is
  241.  *  given by *nacc_addr.  t may be subjected to reallocation if it is not
  242.  *  large enough to hold the epsilon closure.
  243.  *
  244.  *  hashval is the hash value for the dfa corresponding to the state set.
  245.  */
  246.  
  247. int *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr )
  248. int *t, *ns_addr, accset[], *nacc_addr, *hv_addr;
  249.     {
  250.     register int stkpos, ns, tsp;
  251.     int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum;
  252.     int stkend, nstate;
  253.     static int did_stk_init = false, *stk; 
  254.  
  255. #define MARK_STATE(state) \
  256. trans1[state] = trans1[state] - MARKER_DIFFERENCE;
  257.  
  258. #define IS_MARKED(state) (trans1[state] < 0)
  259.  
  260. #define UNMARK_STATE(state) \
  261. trans1[state] = trans1[state] + MARKER_DIFFERENCE;
  262.  
  263. #define CHECK_ACCEPT(state) \
  264. { \
  265. nfaccnum = accptnum[state]; \
  266. if ( nfaccnum != NIL ) \
  267. accset[++nacc] = nfaccnum; \
  268. }
  269.  
  270. #define DO_REALLOCATION \
  271. { \
  272. current_max_dfa_size += MAX_DFA_SIZE_INCREMENT; \
  273. ++num_reallocs; \
  274. t = reallocate_integer_array( t, current_max_dfa_size ); \
  275. stk = reallocate_integer_array( stk, current_max_dfa_size ); \
  276. } \
  277.  
  278. #define PUT_ON_STACK(state) \
  279. { \
  280. if ( ++stkend >= current_max_dfa_size ) \
  281. DO_REALLOCATION \
  282. stk[stkend] = state; \
  283. MARK_STATE(state) \
  284. }
  285.  
  286. #define ADD_STATE(state) \
  287. { \
  288. if ( ++numstates >= current_max_dfa_size ) \
  289. DO_REALLOCATION \
  290. t[numstates] = state; \
  291. hashval += state; \
  292. }
  293.  
  294. #define STACK_STATE(state) \
  295. { \
  296. PUT_ON_STACK(state) \
  297. CHECK_ACCEPT(state) \
  298. if ( nfaccnum != NIL || transchar[state] != SYM_EPSILON ) \
  299. ADD_STATE(state) \
  300. }
  301.  
  302.  
  303.     if ( ! did_stk_init )
  304.         {
  305.         stk = allocate_integer_array( current_max_dfa_size );
  306.         did_stk_init = true;
  307.         }
  308.  
  309.     nacc = stkend = hashval = 0;
  310.  
  311.     for ( nstate = 1; nstate <= numstates; ++nstate )
  312.         {
  313.         ns = t[nstate];
  314.  
  315.         /* The state could be marked if we've already pushed it onto
  316.          * the stack.
  317.          */
  318.         if ( ! IS_MARKED(ns) )
  319.             {
  320.             PUT_ON_STACK(ns)
  321.             CHECK_ACCEPT(ns)
  322.             hashval += ns;
  323.             }
  324.         }
  325.  
  326.     for ( stkpos = 1; stkpos <= stkend; ++stkpos )
  327.         {
  328.         ns = stk[stkpos];
  329.         transsym = transchar[ns];
  330.  
  331.         if ( transsym == SYM_EPSILON )
  332.             {
  333.             tsp = trans1[ns] + MARKER_DIFFERENCE;
  334.  
  335.             if ( tsp != NO_TRANSITION )
  336.                 {
  337.                 if ( ! IS_MARKED(tsp) )
  338.                     STACK_STATE(tsp)
  339.  
  340.                 tsp = trans2[ns];
  341.  
  342.                 if ( tsp != NO_TRANSITION && ! IS_MARKED(tsp) )
  343.                     STACK_STATE(tsp)
  344.                 }
  345.             }
  346.         }
  347.  
  348.     /* Clear out "visit" markers. */
  349.  
  350.     for ( stkpos = 1; stkpos <= stkend; ++stkpos )
  351.         {
  352.         if ( IS_MARKED(stk[stkpos]) )
  353.             UNMARK_STATE(stk[stkpos])
  354.         else
  355.             flexfatal( "consistency check failed in epsclosure()" );
  356.         }
  357.  
  358.     *ns_addr = numstates;
  359.     *hv_addr = hashval;
  360.     *nacc_addr = nacc;
  361.  
  362.     return t;
  363.     }
  364.  
  365.  
  366. /* increase_max_dfas - increase the maximum number of DFAs */
  367.  
  368. void increase_max_dfas()
  369.     {
  370.     current_max_dfas += MAX_DFAS_INCREMENT;
  371.  
  372.     ++num_reallocs;
  373.  
  374.     base = reallocate_integer_array( base, current_max_dfas );
  375.     def = reallocate_integer_array( def, current_max_dfas );
  376.     dfasiz = reallocate_integer_array( dfasiz, current_max_dfas );
  377.     accsiz = reallocate_integer_array( accsiz, current_max_dfas );
  378.     dhash = reallocate_integer_array( dhash, current_max_dfas );
  379.     dss = reallocate_int_ptr_array( dss, current_max_dfas );
  380.     dfaacc = reallocate_dfaacc_union( dfaacc, current_max_dfas );
  381.  
  382.     if ( nultrans )
  383.         nultrans =
  384.             reallocate_integer_array( nultrans, current_max_dfas );
  385.     }
  386.  
  387.  
  388. /* ntod - convert an ndfa to a dfa
  389.  *
  390.  * Creates the dfa corresponding to the ndfa we've constructed.  The
  391.  * dfa starts out in state #1.
  392.  */
  393.  
  394. void ntod()
  395.     {
  396.     int *accset, ds, nacc, newds;
  397.     int sym, hashval, numstates, dsize;
  398.     int num_full_table_rows;    /* used only for -f */
  399.     int *nset, *dset;
  400.     int targptr, totaltrans, i, comstate, comfreq, targ;
  401.     int *epsclosure(), snstods(), symlist[CSIZE + 1];
  402.     int num_start_states;
  403.     int todo_head, todo_next;
  404.  
  405.     /* Note that the following are indexed by *equivalence classes*
  406.      * and not by characters.  Since equivalence classes are indexed
  407.      * beginning with 1, even if the scanner accepts NUL's, this
  408.      * means that (since every character is potentially in its own
  409.      * equivalence class) these arrays must have room for indices
  410.      * from 1 to CSIZE, so their size must be CSIZE + 1.
  411.      */
  412.     int duplist[CSIZE + 1], state[CSIZE + 1];
  413.     int targfreq[CSIZE + 1], targstate[CSIZE + 1];
  414.  
  415.     accset = allocate_integer_array( num_rules + 1 );
  416.     nset = allocate_integer_array( current_max_dfa_size );
  417.  
  418.     /* The "todo" queue is represented by the head, which is the DFA
  419.      * state currently being processed, and the "next", which is the
  420.      * next DFA state number available (not in use).  We depend on the
  421.      * fact that snstods() returns DFA's \in increasing order/, and thus
  422.      * need only know the bounds of the dfas to be processed.
  423.      */
  424.     todo_head = todo_next = 0;
  425.  
  426.     for ( i = 0; i <= csize; ++i )
  427.         {
  428.         duplist[i] = NIL;
  429.         symlist[i] = false;
  430.         }
  431.  
  432.     for ( i = 0; i <= num_rules; ++i )
  433.         accset[i] = NIL;
  434.  
  435.     if ( trace )
  436.         {
  437.         dumpnfa( scset[1] );
  438.         fputs( "\n\nDFA Dump:\n\n", stderr );
  439.         }
  440.  
  441.     inittbl();
  442.  
  443.     /* Check to see whether we should build a separate table for
  444.      * transitions on NUL characters.  We don't do this for full-speed
  445.      * (-F) scanners, since for them we don't have a simple state
  446.      * number lying around with which to index the table.  We also
  447.      * don't bother doing it for scanners unless (1) NUL is in its own
  448.      * equivalence class (indicated by a positive value of
  449.      * ecgroup[NUL]), (2) NUL's equivalence class is the last
  450.      * equivalence class, and (3) the number of equivalence classes is
  451.      * the same as the number of characters.  This latter case comes
  452.      * about when useecs is false or when it's true but every character
  453.      * still manages to land in its own class (unlikely, but it's
  454.      * cheap to check for).  If all these things are true then the
  455.      * character code needed to represent NUL's equivalence class for
  456.      * indexing the tables is going to take one more bit than the
  457.      * number of characters, and therefore we won't be assured of
  458.      * being able to fit it into a YY_CHAR variable.  This rules out
  459.      * storing the transitions in a compressed table, since the code
  460.      * for interpreting them uses a YY_CHAR variable (perhaps it
  461.      * should just use an integer, though; this is worth pondering ...
  462.      * ###).
  463.      *
  464.      * Finally, for full tables, we want the number of entries in the
  465.      * table to be a power of two so the array references go fast (it
  466.      * will just take a shift to compute the major index).  If
  467.      * encoding NUL's transitions in the table will spoil this, we
  468.      * give it its own table (note that this will be the case if we're
  469.      * not using equivalence classes).
  470.      */
  471.  
  472.     /* Note that the test for ecgroup[0] == numecs below accomplishes
  473.      * both (1) and (2) above
  474.      */
  475.     if ( ! fullspd && ecgroup[0] == numecs )
  476.         {
  477.         /* NUL is alone in its equivalence class, which is the
  478.          * last one.
  479.          */
  480.         int use_NUL_table = (numecs == csize);
  481.  
  482.         if ( fulltbl && ! use_NUL_table )
  483.             {
  484.             /* We still may want to use the table if numecs
  485.              * is a power of 2.
  486.              */
  487.             int power_of_two;
  488.  
  489.             for ( power_of_two = 1; power_of_two <= csize;
  490.                   power_of_two *= 2 )
  491.                 if ( numecs == power_of_two )
  492.                     {
  493.                     use_NUL_table = true;
  494.                     break;
  495.                     }
  496.             }
  497.  
  498.         if ( use_NUL_table )
  499.             nultrans = allocate_integer_array( current_max_dfas );
  500.  
  501.         /* From now on, nultrans != nil indicates that we're
  502.          * saving null transitions for later, separate encoding.
  503.          */
  504.         }
  505.  
  506.  
  507.     if ( fullspd )
  508.         {
  509.         for ( i = 0; i <= numecs; ++i )
  510.             state[i] = 0;
  511.  
  512.         place_state( state, 0, 0 );
  513.         dfaacc[i].dfaacc_state = 0;
  514.         }
  515.  
  516.     else if ( fulltbl )
  517.         {
  518.         if ( nultrans )
  519.             /* We won't be including NUL's transitions in the
  520.              * table, so build it for entries from 0 .. numecs - 1.
  521.              */
  522.             num_full_table_rows = numecs;
  523.  
  524.         else
  525.             /* Take into account the fact that we'll be including
  526.              * the NUL entries in the transition table.  Build it
  527.              * from 0 .. numecs.
  528.              */
  529.             num_full_table_rows = numecs + 1;
  530.  
  531.         /* Unless -Ca, declare it "short" because it's a real
  532.          * long-shot that that won't be large enough.
  533.          */
  534.         printf( "static const %s yy_nxt[][%d] =\n    {\n",
  535.             /* '}' so vi doesn't get too confused */
  536.             long_align ? "long" : "short", num_full_table_rows );
  537.  
  538.         /* Generate 0 entries for state #0. */
  539.         for ( i = 0; i < num_full_table_rows; ++i )
  540.             mk2data( 0 );
  541.  
  542.         /* Force ',' and dataflush() next call to mk2data().*/
  543.         datapos = NUMDATAITEMS;
  544.  
  545.         /* Force extra blank line next dataflush(). */
  546.         dataline = NUMDATALINES;
  547.         }
  548.  
  549.     /* Create the first states. */
  550.  
  551.     num_start_states = lastsc * 2;
  552.  
  553.     for ( i = 1; i <= num_start_states; ++i )
  554.         {
  555.         numstates = 1;
  556.  
  557.         /* For each start condition, make one state for the case when
  558.          * we're at the beginning of the line (the '^' operator) and
  559.          * one for the case when we're not.
  560.          */
  561.         if ( i % 2 == 1 )
  562.             nset[numstates] = scset[(i / 2) + 1];
  563.         else
  564.             nset[numstates] =
  565.                 mkbranch( scbol[i / 2], scset[i / 2] );
  566.  
  567.         nset = epsclosure( nset, &numstates, accset, &nacc, &hashval );
  568.  
  569.         if ( snstods( nset, numstates, accset, nacc, hashval, &ds ) )
  570.             {
  571.             numas += nacc;
  572.             totnst += numstates;
  573.             ++todo_next;
  574.  
  575.             if ( variable_trailing_context_rules && nacc > 0 )
  576.                 check_trailing_context( nset, numstates,
  577.                             accset, nacc );
  578.             }
  579.         }
  580.  
  581.     if ( ! fullspd )
  582.         {
  583.         if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) )
  584.             flexfatal(
  585.                 "could not create unique end-of-buffer state" );
  586.  
  587.         ++numas;
  588.         ++num_start_states;
  589.         ++todo_next;
  590.         }
  591.  
  592.     while ( todo_head < todo_next )
  593.         {
  594.         targptr = 0;
  595.         totaltrans = 0;
  596.  
  597.         for ( i = 1; i <= numecs; ++i )
  598.             state[i] = 0;
  599.  
  600.         ds = ++todo_head;
  601.  
  602.         dset = dss[ds];
  603.         dsize = dfasiz[ds];
  604.  
  605.         if ( trace )
  606.             fprintf( stderr, "state # %d:\n", ds );
  607.  
  608.         sympartition( dset, dsize, symlist, duplist );
  609.  
  610.         for ( sym = 1; sym <= numecs; ++sym )
  611.             {
  612.             if ( symlist[sym] )
  613.                 {
  614.                 symlist[sym] = 0;
  615.  
  616.                 if ( duplist[sym] == NIL )
  617.                     {
  618.                     /* Symbol has unique out-transitions. */
  619.                     numstates = symfollowset( dset, dsize,
  620.                                 sym, nset );
  621.                     nset = epsclosure( nset, &numstates,
  622.                         accset, &nacc, &hashval );
  623.  
  624.                     if ( snstods( nset, numstates, accset,
  625.                         nacc, hashval, &newds ) )
  626.                         {
  627.                         totnst = totnst + numstates;
  628.                         ++todo_next;
  629.                         numas += nacc;
  630.  
  631.                         if (
  632.                     variable_trailing_context_rules &&
  633.                             nacc > 0 )
  634.                             check_trailing_context(
  635.                                 nset, numstates,
  636.                                 accset, nacc );
  637.                         }
  638.  
  639.                     state[sym] = newds;
  640.  
  641.                     if ( trace )
  642.                         fprintf( stderr, "\t%d\t%d\n",
  643.                             sym, newds );
  644.  
  645.                     targfreq[++targptr] = 1;
  646.                     targstate[targptr] = newds;
  647.                     ++numuniq;
  648.                     }
  649.  
  650.                 else
  651.                     {
  652.                     /* sym's equivalence class has the same
  653.                      * transitions as duplist(sym)'s
  654.                      * equivalence class.
  655.                      */
  656.                     targ = state[duplist[sym]];
  657.                     state[sym] = targ;
  658.  
  659.                     if ( trace )
  660.                         fprintf( stderr, "\t%d\t%d\n",
  661.                             sym, targ );
  662.  
  663.                     /* Update frequency count for
  664.                      * destination state.
  665.                      */
  666.  
  667.                     i = 0;
  668.                     while ( targstate[++i] != targ )
  669.                         ;
  670.  
  671.                     ++targfreq[i];
  672.                     ++numdup;
  673.                     }
  674.  
  675.                 ++totaltrans;
  676.                 duplist[sym] = NIL;
  677.                 }
  678.             }
  679.  
  680.         numsnpairs = numsnpairs + totaltrans;
  681.  
  682.         if ( caseins && ! useecs )
  683.             {
  684.             register int j;
  685.  
  686.             for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j )
  687.                 state[i] = state[j];
  688.             }
  689.  
  690.         if ( ds > num_start_states )
  691.             check_for_backing_up( ds, state );
  692.  
  693.         if ( nultrans )
  694.             {
  695.             nultrans[ds] = state[NUL_ec];
  696.             state[NUL_ec] = 0;    /* remove transition */
  697.             }
  698.  
  699.         if ( fulltbl )
  700.             {
  701.             /* Supply array's 0-element. */
  702.             if ( ds == end_of_buffer_state )
  703.                 mk2data( -end_of_buffer_state );
  704.             else
  705.                 mk2data( end_of_buffer_state );
  706.  
  707.             for ( i = 1; i < num_full_table_rows; ++i )
  708.                 /* Jams are marked by negative of state
  709.                  * number.
  710.                  */
  711.                 mk2data( state[i] ? state[i] : -ds );
  712.  
  713.             /* Force ',' and dataflush() next call to mk2data().*/
  714.             datapos = NUMDATAITEMS;
  715.  
  716.             /* Force extra blank line next dataflush(). */
  717.             dataline = NUMDATALINES;
  718.             }
  719.  
  720.         else if ( fullspd )
  721.             place_state( state, ds, totaltrans );
  722.  
  723.         else if ( ds == end_of_buffer_state )
  724.             /* Special case this state to make sure it does what
  725.              * it's supposed to, i.e., jam on end-of-buffer.
  726.              */
  727.             stack1( ds, 0, 0, JAMSTATE );
  728.  
  729.         else /* normal, compressed state */
  730.             {
  731.             /* Determine which destination state is the most
  732.              * common, and how many transitions to it there are.
  733.              */
  734.  
  735.             comfreq = 0;
  736.             comstate = 0;
  737.  
  738.             for ( i = 1; i <= targptr; ++i )
  739.                 if ( targfreq[i] > comfreq )
  740.                     {
  741.                     comfreq = targfreq[i];
  742.                     comstate = targstate[i];
  743.                     }
  744.  
  745.             bldtbl( state, ds, totaltrans, comstate, comfreq );
  746.             }
  747.         }
  748.  
  749.     if ( fulltbl )
  750.         dataend();
  751.  
  752.     else if ( ! fullspd )
  753.         {
  754.         cmptmps();  /* create compressed template entries */
  755.  
  756.         /* Create tables for all the states with only one
  757.          * out-transition.
  758.          */
  759.         while ( onesp > 0 )
  760.             {
  761.             mk1tbl( onestate[onesp], onesym[onesp], onenext[onesp],
  762.             onedef[onesp] );
  763.             --onesp;
  764.             }
  765.  
  766.         mkdeftbl();
  767.         }
  768.  
  769.     flex_free( (void *) accset );
  770.     flex_free( (void *) nset );
  771.     }
  772.  
  773.  
  774. /* snstods - converts a set of ndfa states into a dfa state
  775.  *
  776.  * synopsis
  777.  *    is_new_state = snstods( int sns[numstates], int numstates,
  778.  *                int accset[num_rules+1], int nacc,
  779.  *                int hashval, int *newds_addr );
  780.  *
  781.  * On return, the dfa state number is in newds.
  782.  */
  783.  
  784. int snstods( sns, numstates, accset, nacc, hashval, newds_addr )
  785. int sns[], numstates, accset[], nacc, hashval, *newds_addr;
  786.     {
  787.     int didsort = 0;
  788.     register int i, j;
  789.     int newds, *oldsns;
  790.  
  791.     for ( i = 1; i <= lastdfa; ++i )
  792.         if ( hashval == dhash[i] )
  793.             {
  794.             if ( numstates == dfasiz[i] )
  795.                 {
  796.                 oldsns = dss[i];
  797.  
  798.                 if ( ! didsort )
  799.                     {
  800.                     /* We sort the states in sns so we
  801.                      * can compare it to oldsns quickly.
  802.                      * We use bubble because there probably
  803.                      * aren't very many states.
  804.                      */
  805.                     bubble( sns, numstates );
  806.                     didsort = 1;
  807.                     }
  808.  
  809.                 for ( j = 1; j <= numstates; ++j )
  810.                     if ( sns[j] != oldsns[j] )
  811.                         break;
  812.  
  813.                 if ( j > numstates )
  814.                     {
  815.                     ++dfaeql;
  816.                     *newds_addr = i;
  817.                     return 0;
  818.                     }
  819.  
  820.                 ++hshcol;
  821.                 }
  822.  
  823.             else
  824.                 ++hshsave;
  825.             }
  826.  
  827.     /* Make a new dfa. */
  828.  
  829.     if ( ++lastdfa >= current_max_dfas )
  830.         increase_max_dfas();
  831.  
  832.     newds = lastdfa;
  833.  
  834.     dss[newds] = allocate_integer_array( numstates + 1 );
  835.  
  836.     /* If we haven't already sorted the states in sns, we do so now,
  837.      * so that future comparisons with it can be made quickly.
  838.      */
  839.  
  840.     if ( ! didsort )
  841.         bubble( sns, numstates );
  842.  
  843.     for ( i = 1; i <= numstates; ++i )
  844.         dss[newds][i] = sns[i];
  845.  
  846.     dfasiz[newds] = numstates;
  847.     dhash[newds] = hashval;
  848.  
  849.     if ( nacc == 0 )
  850.         {
  851.         if ( reject )
  852.             dfaacc[newds].dfaacc_set = (int *) 0;
  853.         else
  854.             dfaacc[newds].dfaacc_state = 0;
  855.  
  856.         accsiz[newds] = 0;
  857.         }
  858.  
  859.     else if ( reject )
  860.         {
  861.         /* We sort the accepting set in increasing order so the
  862.          * disambiguating rule that the first rule listed is considered
  863.          * match in the event of ties will work.  We use a bubble
  864.          * sort since the list is probably quite small.
  865.          */
  866.  
  867.         bubble( accset, nacc );
  868.  
  869.         dfaacc[newds].dfaacc_set = allocate_integer_array( nacc + 1 );
  870.  
  871.         /* Save the accepting set for later */
  872.         for ( i = 1; i <= nacc; ++i )
  873.             {
  874.             dfaacc[newds].dfaacc_set[i] = accset[i];
  875.  
  876.             if ( accset[i] <= num_rules )
  877.                 /* Who knows, perhaps a REJECT can yield
  878.                  * this rule.
  879.                  */
  880.                 rule_useful[accset[i]] = true;
  881.             }
  882.  
  883.         accsiz[newds] = nacc;
  884.         }
  885.  
  886.     else
  887.         {
  888.         /* Find lowest numbered rule so the disambiguating rule
  889.          * will work.
  890.          */
  891.         j = num_rules + 1;
  892.  
  893.         for ( i = 1; i <= nacc; ++i )
  894.             if ( accset[i] < j )
  895.                 j = accset[i];
  896.  
  897.         dfaacc[newds].dfaacc_state = j;
  898.  
  899.         if ( j <= num_rules )
  900.             rule_useful[j] = true;
  901.         }
  902.  
  903.     *newds_addr = newds;
  904.  
  905.     return 1;
  906.     }
  907.  
  908.  
  909. /* symfollowset - follow the symbol transitions one step
  910.  *
  911.  * synopsis
  912.  *    numstates = symfollowset( int ds[current_max_dfa_size], int dsize,
  913.  *                int transsym, int nset[current_max_dfa_size] );
  914.  */
  915.  
  916. int symfollowset( ds, dsize, transsym, nset )
  917. int ds[], dsize, transsym, nset[];
  918.     {
  919.     int ns, tsp, sym, i, j, lenccl, ch, numstates, ccllist;
  920.  
  921.     numstates = 0;
  922.  
  923.     for ( i = 1; i <= dsize; ++i )
  924.         { /* for each nfa state ns in the state set of ds */
  925.         ns = ds[i];
  926.         sym = transchar[ns];
  927.         tsp = trans1[ns];
  928.  
  929.         if ( sym < 0 )
  930.             { /* it's a character class */
  931.             sym = -sym;
  932.             ccllist = cclmap[sym];
  933.             lenccl = ccllen[sym];
  934.  
  935.             if ( cclng[sym] )
  936.                 {
  937.                 for ( j = 0; j < lenccl; ++j )
  938.                     {
  939.                     /* Loop through negated character
  940.                      * class.
  941.                      */
  942.                     ch = ccltbl[ccllist + j];
  943.  
  944.                     if ( ch == 0 )
  945.                         ch = NUL_ec;
  946.  
  947.                     if ( ch > transsym )
  948.                         /* Transsym isn't in negated
  949.                          * ccl.
  950.                          */
  951.                         break;
  952.  
  953.                     else if ( ch == transsym )
  954.                         /* next 2 */ goto bottom;
  955.                     }
  956.  
  957.                 /* Didn't find transsym in ccl. */
  958.                 nset[++numstates] = tsp;
  959.                 }
  960.  
  961.             else
  962.                 for ( j = 0; j < lenccl; ++j )
  963.                     {
  964.                     ch = ccltbl[ccllist + j];
  965.  
  966.                     if ( ch == 0 )
  967.                         ch = NUL_ec;
  968.  
  969.                     if ( ch > transsym )
  970.                         break;
  971.                     else if ( ch == transsym )
  972.                         {
  973.                         nset[++numstates] = tsp;
  974.                         break;
  975.                         }
  976.                     }
  977.             }
  978.  
  979.         else if ( sym >= 'A' && sym <= 'Z' && caseins )
  980.             flexfatal( "consistency check failed in symfollowset" );
  981.  
  982.         else if ( sym == SYM_EPSILON )
  983.             { /* do nothing */
  984.             }
  985.  
  986.         else if ( ABS( ecgroup[sym] ) == transsym )
  987.             nset[++numstates] = tsp;
  988.  
  989.         bottom: ;
  990.         }
  991.  
  992.     return numstates;
  993.     }
  994.  
  995.  
  996. /* sympartition - partition characters with same out-transitions
  997.  *
  998.  * synopsis
  999.  *    sympartition( int ds[current_max_dfa_size], int numstates,
  1000.  *            int symlist[numecs], int duplist[numecs] );
  1001.  */
  1002.  
  1003. void sympartition( ds, numstates, symlist, duplist )
  1004. int ds[], numstates;
  1005. int symlist[], duplist[];
  1006.     {
  1007.     int tch, i, j, k, ns, dupfwd[CSIZE + 1], lenccl, cclp, ich;
  1008.  
  1009.     /* Partitioning is done by creating equivalence classes for those
  1010.      * characters which have out-transitions from the given state.  Thus
  1011.      * we are really creating equivalence classes of equivalence classes.
  1012.      */
  1013.  
  1014.     for ( i = 1; i <= numecs; ++i )
  1015.         { /* initialize equivalence class list */
  1016.         duplist[i] = i - 1;
  1017.         dupfwd[i] = i + 1;
  1018.         }
  1019.  
  1020.     duplist[1] = NIL;
  1021.     dupfwd[numecs] = NIL;
  1022.  
  1023.     for ( i = 1; i <= numstates; ++i )
  1024.         {
  1025.         ns = ds[i];
  1026.         tch = transchar[ns];
  1027.  
  1028.         if ( tch != SYM_EPSILON )
  1029.             {
  1030.             if ( tch < -lastccl || tch >= csize )
  1031.                 {
  1032.                 flexfatal(
  1033.             "bad transition character detected in sympartition()" );
  1034.                 }
  1035.  
  1036.             if ( tch >= 0 )
  1037.                 { /* character transition */
  1038.                 int ec = ecgroup[tch];
  1039.  
  1040.                 mkechar( ec, dupfwd, duplist );
  1041.                 symlist[ec] = 1;
  1042.                 }
  1043.  
  1044.             else
  1045.                 { /* character class */
  1046.                 tch = -tch;
  1047.  
  1048.                 lenccl = ccllen[tch];
  1049.                 cclp = cclmap[tch];
  1050.                 mkeccl( ccltbl + cclp, lenccl, dupfwd,
  1051.                     duplist, numecs, NUL_ec );
  1052.  
  1053.                 if ( cclng[tch] )
  1054.                     {
  1055.                     j = 0;
  1056.  
  1057.                     for ( k = 0; k < lenccl; ++k )
  1058.                         {
  1059.                         ich = ccltbl[cclp + k];
  1060.  
  1061.                         if ( ich == 0 )
  1062.                             ich = NUL_ec;
  1063.  
  1064.                         for ( ++j; j < ich; ++j )
  1065.                             symlist[j] = 1;
  1066.                         }
  1067.  
  1068.                     for ( ++j; j <= numecs; ++j )
  1069.                         symlist[j] = 1;
  1070.                     }
  1071.  
  1072.                 else
  1073.                     for ( k = 0; k < lenccl; ++k )
  1074.                         {
  1075.                         ich = ccltbl[cclp + k];
  1076.  
  1077.                         if ( ich == 0 )
  1078.                             ich = NUL_ec;
  1079.  
  1080.                         symlist[ich] = 1;
  1081.                         }
  1082.                 }
  1083.             }
  1084.         }
  1085.     }
  1086.